\section{\href{https://www.apiref.com/cpp-zh/cpp/header/numeric.html}{std::numeric}}
\begin{itemize}
    \item \href{https://www.apiref.com/cpp-zh/cpp/algorithm/accumulate.html}{accumulate}：实现对迭代器中元素的求和，通过指定 binary\_op 可以实现不同的功能。
    \item \href{https://www.apiref.com/cpp-zh/cpp/algorithm/adjacent_difference.html}{adjacent\_difference}:计算临近范围的差。
    \item \href{https://www.apiref.com/cpp-zh/cpp/algorithm/inner_product.html}{inner\_product}:计算迭代器指向范围内的累计和。
    \item \href{https://www.apiref.com/cpp-zh/cpp/algorithm/iota.html}{iota}(C++11): 存储递增序列
    \item \href{https://www.apiref.com/cpp-zh/cpp/algorithm/partial_sum.html}{partial\_sum}: 计算范围内的部分和。
    \item \href{https://www.apiref.com/cpp-zh/cpp/algorithm/transform_reduce.html}{transform\_reduce}：
    \item \href{https://www.apiref.com/cpp-zh/cpp/algorithm/inclusive_scan.html}{inclusive\_scan}：扫描区间，对区间的数据使用binary\_op。
    \item \href{https://www.apiref.com/cpp-zh/cpp/algorithm/transform_inclusive_scan.html}{transform\_inclusive\_scan}(C++17)：扫描区间，对区间的数据先变换然后使用binary\_op。
	\item \href{https://www.apiref.com/cpp-zh/cpp/algorithm/transform_exclusive_scan.html}{transform\_exclusive\_scan}(C++17)：同上，区别在于是否包含迭代器指向的元素，即[first,last)。
    \item \href{https://www.apiref.com/cpp-zh/cpp/numeric/gcd.html}{gcd}(C++17)返回二个整数最大公约数的 constexpr 函数模板(函数模板)。
    \item \href{https://www.apiref.com/cpp-zh/cpp/numeric/lcm.html}{lcm}(C++17)返回二个整数最小公倍数的 constexpr 函数模板(函数模板)。
    \item \href{https://www.apiref.com/cpp-zh/cpp/numeric/midpoint.html}{midpoint}(C++20)：两个数值或指针间的中点。
\end{itemize}
\subsection{std::accumulate}
accumulate 迭代计算的流程：
初始值作为binrary\_op第一个参数，迭代器指向的元素作为 binary\_op 第二个元素，然后调用函数计算，计算结果作为下次迭代的第一个参数，迭代器右移，直到移动到第二个迭代器指向位置的前一个位置[first,second)。例如数据 [1,2,3,4,5,6,7,8]，计算为 x+4*y，初始值为0。如\figref{fig:accumulate}
\begin{itemize}
    \item 初始计算参数0,1。0+1*4=4，下次计算的时候是4、2。
    \item 4+4*2=12，下次计算的时候是12、3。
    \item 12+4*3=24，下次计算的时候是24、4。
    \item 24+4*4=40，下次计算的时候是40、5。
    \item 40+4*5=60，下次计算的时候是60、6。
    \item 60+4*6=84，下次计算的时候是84、7。
    \item 84+4*7=112，已经到了最后一个元素，结束计算。
\end{itemize}
\begin{figure}[!htbp]
    \centering
    \includegraphics[width=\textwidth]{accumulate}
    \caption{accumulate 计算示意图}
    \label{fig:accumulate}
\end{figure}
\cppfile{sample/numeric_accumulate_demo.cc}
\begin{remark}
    \begin{itemize}
        \item accumulate(data,data+7,0,[](int x,int y){return x+4*y;}) 类似于 python中的reduce(lambda x,y:x+y,[0]+data)。
        \item 区间为[data,data+offset)，右边为开区间。
    \end{itemize}
\end{remark}
\subsection{std::adjacent\_difference}
adjacent\_difference 的计算流程(假设数组x只有5个元素)和 最终返回的是数组：
\begin{enumerate}
    \item $y_0 = x_0$
    \item $y_1 = x_1 - x_0$
    \item $y_2 = x_2 - x_1$
    \item $y_3 = x_3 - x_2$
    \item $y_4 = x_4 - x_3$
\end{enumerate}
\cppfile{sample/numeric_adjacent_difference_demo.cc}
\subsection{std::inner\_product}
函数签名：
\begin{cpp}
template< class InputIt1, class InputIt2, class T >
T inner_product( InputIt1 first1, InputIt1 last1,InputIt2 first2, T init );//(C++20 前)
template< class InputIt1, class InputIt2, class T >
constexpr T inner_product( InputIt1 first1, InputIt1 last1,InputIt2 first2, T init );//(C++20 起)
template<class InputIt1, class InputIt2, class T,class BinaryOperation1, class BinaryOperation2>
T inner_product( InputIt1 first1, InputIt1 last1,InputIt2 first2, T init,BinaryOperation1 op1,BinaryOperation2 op2 );//(C++20 前)
template<class InputIt1, class InputIt2, class T,class BinaryOperation1, class BinaryOperation2>
constexpr T inner_product( InputIt1 first1, InputIt1 last1,InputIt2 first2, T init,BinaryOperation1 op1,BinaryOperation2 op2 );//(C++20 起)
\end{cpp}
计算内积（即积之和）或在范围 [first1, last1) 和始于 first2 的范围上进行有序映射/规约操作。
\begin{enumerate}
    \item 以初值 init 初始化积累器 acc ，然后
        \begin{itemize}
            \item 以表达式 acc = acc + *first1 * *first2 修改它，再以表达式 acc = acc + *(first1+1) * *(first2+1) 修改它，以此类推(C++20 前)
            \item 以表达式 acc = std::move(acc) + *first1 * *first2 修改它，再以表达式 acc = std::move(acc) + *(first1+1) * *(first2+1) 修改它，以此类推(C++20 起)直至抵达 last1 。对于 + 与 * 的内建含义，此算法计算二个范围的内积。
        \end{itemize}
    \item 以初值 init 初始化积累器 acc ，然后
        \begin{itemize}
            \item 以表达式 acc = op1(acc, op2(*first1, *first2)) 修改它，再以表达式 acc = op1(acc, op2(*(first1+1), *(first2+1))) 修改它，以此类推(C++20 前)
            \item 以表达式 acc = op1(std::move(acc), op2(*first1, *first2)) 修改它，再以表达式 acc = op1(std::move(acc), op2(*(first1+1), *(first2+1))) 修改它，以此类推(C++20 起)
直至抵达 last1 。
        \end{itemize}
\end{enumerate}
\begin{remark}
    \begin{itemize}
        \item op1 或 op2 必须无副作用。(C++11 前)
        \item op1 或 op2 必须不非法化所涉及范围的任何迭代器，含尾迭代器或修改该范围的任何元素。(C++11 起)
    \end{itemize}
    \end{remark}
计算如下:
\begin{enumerate}
    \item 初始化init值。
    \item op(*first++)
\end{enumerate}
inner\_product 计算两个迭代器中对应元素的乘积然后累积求和，此函数可以接受两个函数对象 op1 和 op2。此操作可以对第二个迭代器指向的数组用op2操作，然后用op1 操作初始化数据和 op2 的结果。例如，代码中的case2计算流程如下\figref{fig:inner_product}：
\begin{itemize}
    \item 使用divides函数计算 [10/1,20/2,30/2]
    \item 使用init作为初始值，通过op计算reduce操作。100-10-10-10=70
\end{itemize}
\cppfile{sample/numeric_inner_product_demo.cc}
\begin{figure}[!htbp]
\centering
    \includegraphics[width=\textwidth]{inner_product}
    \caption{inner\_product 计算示意图}
    \label{fig:inner_product}
\end{figure}
\subsection{std::iota}
iota：原地修改迭代器中的元素，每次修改之后元素都会+1。
\cppfile{sample/numeric_iota_demo.cc}
\subsection{std::partial\_sum}
对迭代器指向内容的部分内容求和，类似于cumsum。
\begin{itemize}
    \item $y_0 = x_0$
    \item $y_1 = x_0 + x_1$
    \item $y_2 = x_0 + x_1 + x_2$
    \item $y_3 = x_0 + x_1 + x_2 + x_3$
    \item $y_4 = x_0 + x_1 + x_2 + x_3 + x_4$
\end{itemize}
\cppfile{sample/numeric_partial_sum_demo.cc}
\subsection{std::transform\_reduce}
\begin{cpp}
template<class InputIt1, class InputIt2, class T>
T transform_reduce(InputIt1 first1, InputIt1 last1, InputIt2 first2, T init); //(C++17 起) (C++20 前)
template<class InputIt1, class InputIt2, class T>
constexpr T transform_reduce(InputIt1 first1, InputIt1 last1, InputIt2 first2, T init);//(C++20 起)
template <class InputIt1, class InputIt2, class T, class BinaryOp1, class BinaryOp2>
T transform_reduce(InputIt1 first1, InputIt1 last1, InputIt2 first2,
                   T init, BinaryOp1 binary_op1, BinaryOp2 binary_op2);//(C++17 起) (C++20 前)
template <class InputIt1, class InputIt2, class T, class BinaryOp1, class BinaryOp2>
constexpr T transform_reduce(InputIt1 first1, InputIt1 last1, InputIt2 first2,
                             T init, BinaryOp1 binary_op1, BinaryOp2 binary_op2);//(C++20 起)
template<class InputIt, class T, class BinaryOp, class UnaryOp>
T transform_reduce(InputIt first, InputIt last,
                   T init, BinaryOp binop, UnaryOp unary_op);//(C++17 起)(C++20 前)
template<class InputIt, class T, class BinaryOp, class UnaryOp>
constexpr T transform_reduce(InputIt first, InputIt last,
                             T init, BinaryOp binop, UnaryOp unary_op);//(C++20 起)
template<class ExecutionPolicy,
         class ForwardIt1, class ForwardIt2, class T>
T transform_reduce(ExecutionPolicy&& policy,
                   ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, T init);//(C++17 起)
template<class ExecutionPolicy,
         class ForwardIt1, class ForwardIt2, class T, class BinaryOp1, class BinaryOp2>
T transform_reduce(ExecutionPolicy&& policy,
                   ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2,
                   T init, BinaryOp1 binary_op1, BinaryOp2 binary_op2);//(C++17 起)
template<class ExecutionPolicy,
         class ForwardIt, class T, class BinaryOp, class UnaryOp>
T transform_reduce(ExecutionPolicy&& policy,
                   ForwardIt first, ForwardIt last,
                   T init, BinaryOp binary_op, UnaryOp unary_op);//    (C++17 起)

\end{cpp}
\begin{enumerate}
    \item 等价于 transform\_reduce(first1, last1, first2, init, std::plus<>(), std::multiplies<>()); ，默认的 std::inner\_product 的等效并行版本
    \item 应用 binary\_op2 到来自范围 [first; last) 和始于 first2 的范围的每对元素，并在 binary\_op1 上与初始值 init 一同规约结果（可以以未指定行为重排聚合）
    \item 应用 unary\_op 到范围 [first; last) 中的每个元素，并在 binary\_op 上与初始值 init 一同规约结果（可以以未指定行为重排聚合）。
    \item  同 (1-3) ，但按照 policy 执行。这些重载仅若 std::is\_execution\_policy\_v<std::decay\_t<ExecutionPolicy>> (C++20 前)std::is\_execution\_policy\_v<std::remove\_cvref\_t<ExecutionPolicy>> (C++20 起) 为 true 才参与重载决议。
\end{enumerate}
\begin{itemize}
    \item 若 binary\_op/binary\_op2 为非交换或非结合则行为不确定。
    \item 若 unary\_op 、 binary\_op 、 binary\_op1 或 binary\_op2 修改输入范围中的任何元素或非法化范围中的任何迭代器，含尾迭代器，则行为未定义。
\end{itemize}
参数
\begin{itemize}
    \item first, last：要应用算法的元素范围
    \item init：广义和的初始值
    \item policy：使用的执行策略，细节见执行策略。
    \item unary\_op：将应用于输入范围的每个元素的一元函数对象 (FunctionObject) 。返回类型必须可为 binary\_op 的输入所接受
    \item binary\_op：将以未指定顺序应用于 unary\_op 的结果、其他 binary\_op 的结果和 init 的二元函数对象 (FunctionObject) 。
\end{itemize}
类型要求
%- 为使用重载 (3,6) ， T 必须满足可移动构造 (MoveConstructible) 的要求。且表达式 binary_op(init, unary_op(*first)) 、 binary_op(unary_op(*first), init) 、 binary_op(init, init) 和 binary_op(unary_op(*first), unary_op(*first)) 的结果必须可转换为 T
%- 为使用重载 (2,5) ， T 必须满足可移动构造 (MoveConstructible) 的要求。且表达式 binary_op1(init, binary_op2(*first1, *first2)) 、 binary_op1(binary_op2(*first1, *first2), init) 、 binary_op1(init, init) 和 binary_op1(binary_op2(*first1, *first2), binary_op2(*first1, *first2)) 的结果必须可转换为 T
%-InputIt 必须满足遗留输入迭代器 (LegacyInputIterator) 的要求。
%-ForwardIt 必须满足遗留向前迭代器 (LegacyForwardIterator) 的要求。
%返回值
%2) init 和 binary_op2(*first,*first2) 、 binary_op2(*(first+1),*(first2+1)) ……在 binary_op1 上的广义和
%3) init 和 unary_op(*first) 、 unary_op(*(first+1)) …… unary_op(*(last-1)) 在 binary_op 上的广义和，
%其中广义和 GSUM(op, a
%1, ..., a
%N) 定义如下：
%
%若 N=1 ，则为 a
%1
%若 N > 1 ，则为 op(GSUM(op, b
%1, ..., b
%K), GSUM(op, b
%M, ..., b
%N)) ，其中
%b
%1, ..., b
%N 可以是 a1, ..., aN 的任意重排，若
%1 < K+1 = M ≤ N
%换言之， unary_op 或 binary_op1 的结果能以任意顺序组合排列。
%
%复杂度
%1,2,4,5) 各使用 O(last1 - first1) 次 binary_op1 和 binary_op2 。
%3,6) 各使用 O(last - first) 次 unary_op 和 binary_op 。
%异常
%拥有名为 ExecutionPolicy 的模板形参的重载按下列方式报告错误：
%
%若作为算法一部分调用的函数的执行抛出异常，且 ExecutionPolicy 为标准策略之一，则调用 std::terminate 。对于任何其他 ExecutionPolicy ，行为是实现定义的。
%若算法无法分配内存，则抛出 std::bad_alloc 。
%注解
%在一元-二元重载 (3,6) 中， unary_op 不应用到 init
%
%若 first == last 或 first1 == last1 ，则返回不修改的 init
%
%示例
%transform_reduce 能用于并行化的 std::inner_product ：
%
%运行此代码
%#include <vector>
%#include <functional>
%#include <iostream>
%#include <numeric>
%#include <execution>
% 
%int main()
%{
%    std::vector<double> xvalues(10007, 1.0), yvalues(10007, 1.0);
% 
%    double result = std::transform_reduce(
%        std::execution::par,
%        xvalues.begin(), xvalues.end(),
%        yvalues.begin(), 0.0
%    );
%    std::cout << result << '\n';
%}
%输出：
%
%10007
\subsection{\href{https://www.apiref.com/cpp-zh/cpp/algorithm/inclusive_scan.html}{std::inclusive\_scan(C++17)}}
\begin{cpp}
template< class InputIt, class OutputIt >
OutputIt inclusive_scan( InputIt first,
                         InputIt last, OutputIt d_first );//(C++17 起
(C++20 前)
template< class InputIt, class OutputIt >
constexpr OutputIt inclusive_scan( InputIt first,
                                   InputIt last, OutputIt d_first );//(C++20 起)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
ForwardtIt2 inclusive_scan( ExecutionPolicy&& policy, ForwardIt1 first,
                            ForwardIt1 last, ForwardIt2 d_first );//(2)    (C++17 起)
(3)    
template< class InputIt, class OutputIt, class BinaryOperation >
OutputIt inclusive_scan( InputIt first, InputIt last,
                         OutputIt d_first, BinaryOperation binary_op );//(C++17 起) (C++20 前)
template< class InputIt, class OutputIt, class BinaryOperation >
constexpr OutputIt inclusive_scan( InputIt first, InputIt last,
                                   OutputIt d_first, BinaryOperation binary_op );//(C++20 起)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
          class BinaryOperation >
ForwardIt2 inclusive_scan( ExecutionPolicy&& policy,
                           ForwardIt1 first, ForwardIt1 last,
                           ForwardIt2 d_first, BinaryOperation binary_op );//(4)    (C++17 起)     
template< class InputIt, class OutputIt, class BinaryOperation, class T >
OutputIt inclusive_scan( InputIt first, InputIt last, OutputIt d_first,
                         BinaryOperation binary_op, T init );//(C++17 起) (C++20 前)
template< class InputIt, class OutputIt, class BinaryOperation, class T >
constexpr OutputIt inclusive_scan( InputIt first, InputIt last, OutputIt d_first,
                                   BinaryOperation binary_op, T init );(C++20 起)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
          class BinaryOperation, class T >
ForwardIt2 inclusive_scan( ExecutionPolicy&& policy,
                           ForwardIt1 first, ForwardIt1 last, ForwardIt2 d_first,
                           BinaryOperation binary_op, T init );
(6)    (C++17 起)
\end{cpp}
用 binary\_op操作 （或对于重载 (1-2) 则是 std::plus<>() ）对迭代器范围 [first, last)中的数据拿出来运算，以 init 为初始值（若提供），并将结果写入 d\_first 指向的数据范围。“包含性”意味着\textcolor{blue}{第 i 个输入元素包含于第 i 个和}。

通过每个 [d\_first, d\_first + (last - first)) 中的迭代器 i ，以下列值赋值：
\begin{itemize}
    \item 重载 (1-4)实现为，对于每个区间 [first, first + (i - d\_first + 1)) 中的 j ， *j... 在 binary\_op 上的广义非交换和。
    \item 重载 (5-6)实现为，对于每个区间 [first, first + (i - d\_first + 1)) 中的 j ， init, *j... 在 binary\_op 上的广义非交换和其中广义非交换和 $GNSUM(op, a_1, \ldots, a_N)$ 定义如下：
        \begin{equation}
            \begin{cases}
                a_1\quad N = 1 \\
                op(GNSUM(op,a_1,\ldots,a_k),GNSUM(op,a_M,\ldots,a_N))\quad 1 < K+1 = M \leq N\\
            \end{cases}
        \end{equation}
\end{itemize}
和运算可能以任意顺序进行，而且若 binary\_op 非结合，则行为是非确定的。
重载 (2,4,6) 按照 policy 执行。这些重载仅若 std::is\_execution\_policy\_v <std::decay\_t<ExecutionPolicy>> (C++20 前) std::is\_execution\_policy\_v<std::remove\_cvref\_t<ExecutionPolicy>> (C++20 起) 为 true 才参与重载决议。

\textbf{参数}
\begin{itemize}
    \item first, last：要求和的元素范围。
    \item d\_first：目标范围的起始，可以等于 first。
    \item policy：所用的执行策略。细节见\href{https://www.apiref.com/cpp-zh/cpp/algorithm/execution_policy_tag_t.html}{执行策略}。
    \item init：初始值（可选）。
    \item binary\_op：将应用到解引用输入迭代器结果、其他 binary\_op 结果和 init （若提供）的二元函数对象 (FunctionObject) 。
\end{itemize}
类型要求
\begin{itemize}
    \item InputIt 必须满足遗留输入迭代器 (LegacyInputIterator) 的要求。
    \item OutputIt 必须满足遗留输出迭代器 (LegacyOutputIterator) 的要求。
    \item ForwardIt1 必须满足遗留向前迭代器 (LegacyForwardIterator) 的要求。
    \item ForwardIt2 必须满足遗留向前迭代器 (LegacyForwardIterator) 的要求。
    \item 若不提供 init ，则 decltype(first) 的值类型必须为可移动构造 (MoveConstructible) 且 binary\_op(*first, *first) 必须可转换成 decltype(first) 的值类型。
\item T （若提供 init ） 必须满足可移动构造 (MoveConstructible) 的要求。binary\_op(init, *first) 、 binary\_op(init, init) 及 binary\_op(*first, *first) 都必须能转换到 T
\end{itemize}
\textbf{返回值}:指向最后写入元素后一位的迭代器。

\textbf{复杂度}:O(last - first) 次应用二元运算

\textbf{异常}:
拥有名为 ExecutionPolicy 的模板形参的重载按下列方式报告错误：
\begin{itemize}
    \item 若作为算法一部分调用的函数的执行抛出异常，且 ExecutionPolicy 为标准策略之一，则调用 std::terminate 。对于任何其他 ExecutionPolicy ，行为是实现定义的。
    \item 若算法无法分配内存，则抛出 std::bad\_alloc 。
\end{itemize}
示意图如\figref{fig:inclusive_scan}
\begin{figure}[!htbp]
    \centering
    \includegraphics[width=\textwidth]{inclusive_scan}
    \caption{std::inclusive\_scan示意图}
    \label{fig:inclusive_scan}
\end{figure}
\subsection{\href{https://www.apiref.com/cpp-zh/cpp/algorithm/exclusive_scan.html}{std::exclusive\_scan}}
定义于头文件 <numeric>
\begin{cpp}
(1)
template< class InputIt, class OutputIt, class T >
OutputIt exclusive_scan( InputIt first, InputIt last,
                         OutputIt d_first, T init );// (C++17 起)(C++20 前)
template< class InputIt, class OutputIt, class T >
constexpr OutputIt exclusive_scan( InputIt first, InputIt last,
                                   OutputIt d_first, T init );// (C++20 起)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class T >
ForwardIt2 exclusive_scan( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last,
                           ForwardIt2 d_first, T init); //(2)    (C++17 起) (3)
template< class InputIt, class OutputIt,
          class T, class BinaryOperation >
OutputIt exclusive_scan( InputIt first, InputIt last,
                         OutputIt d_first, T init, BinaryOperation binary_op ); // (C++17 起) (C++20 前)
template< class InputIt, class OutputIt,
          class T, class BinaryOperation >
constexpr OutputIt exclusive_scan( InputIt first, InputIt last,
                                   OutputIt d_first, T init, BinaryOperation binary_op );// (C++20 起)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
          class T, class BinaryOperation >
ForwardIt2 exclusive_scan( ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last,
                           ForwardIt2 d_first, T init, BinaryOperation binary_op );// (4)    (C++17 起)
\end{cpp}
用 binary\_op （或对于重载 (1-2) 是 std::plus<>() ）计算范围 [first, last) 上排除性前缀和，以 init 为初始值，并写入结果到从 d\_first 开始的范围。“排除性”表示\textcolor{blue}{第 i 个输入元素不包含于第 i 个和}。

正式而言，用对于 [first, first + (i - d\_first)) 中的每个 j 在 binary\_op 上的广义非交换和 init, *j... 的值，通过 [d\_first, d\_first + (last - first)) 中的每个迭代器赋值。

其中广义非交换和 $GNSUM(op, a_1, \ldots, a_N)$ 定义如下：
\begin{equation}
    \begin{cases}
        a_1 \quad N = 1 \\
        op(GNSUM(op, a_1,\ldots, a_K), GNSUM(op, a_M, \ldots, a_N)) \quad  1 < K+1 = M \leq N 
    \end{cases}
\end{equation}
换言之，和运算可能以任意顺序进行，而且若 binary\_op 非结合，则行为是非确定的。

重载 (2,4) 按照 policy 执行。这些重载仅若 std::is\_execution\_policy\_v<std::decay\_t<ExecutionPolicy>> (C++20 前) std::is\_execution\_policy\_v<std::remove\_cvref\_t<ExecutionPolicy>> (C++20 起) 为 true 才参与重载决议。

binary\_op 不应非法化范围 [first, last) 或 [d\_first, d\_first + (last - first)) 中的迭代器（含尾迭代器）或子范围，亦不应修改其中的元素。否则行为未定义。

参数
\begin{itemize}
    \item first, last：要求和的元素范围
    \item d\_first：目标范围的起始；可以等于 first
    \item policy：所用的执行策略。细节见执行策略。
    \item init：初始值
    \item binary\_op：将应用到解引用输入迭代器的结果、其他 binary\_op 的结果和 init 的二元函数对象 (FunctionObject) 。
\end{itemize}
类型要求
\begin{itemize}
    \item InputIt 必须满足遗留输入迭代器 (LegacyInputIterator) 的要求。
    \item OutputIt 必须满足遗留输出迭代器 (LegacyOutputIterator) 的要求。
    \item ForwardIt1, ForwardIt2 必须满足遗留向前迭代器 (LegacyForwardIterator) 的要求。
    \item T 必须满足可移动构造 (MoveConstructible) 的要求。且 binary\_op(init, *first) 、 binary\_op(init, init) 及 binary\_op(*first, *first) 必须能转换到 T
\end{itemize}
\textbf{返回值}：指向最后写入元素的后一元素的迭代器。

\textbf{复杂度}:O(last - first) 次应用二元运算

\textbf{异常} 拥有名为 ExecutionPolicy 的模板形参的重载按下列方式报告错误：
\begin{itemize}
    \item 若作为算法一部分调用的函数的执行抛出异常，且 ExecutionPolicy 为标准策略之一，则调用 std::terminate 。对于任何其他 ExecutionPolicy ，行为是实现定义的。
    \item 若算法无法分配内存，则抛出 std::bad\_alloc 。
\end{itemize}
\cppfile{sample/numeric_exclusive_demo.cc}
示意图如\figref{fig:exclusive_scan}：
\begin{figure}[!htbp]
    \centering
    \includegraphics[width=\textwidth]{exclusive_scan}
    \caption{std::exclusive\_scan计算示意图}
    \label{fig:exclusive_scan}
\end{figure}
\subsection{\href{https://www.apiref.com/cpp-zh/cpp/algorithm/transform_inclusive_scan.html}{std::transform\_inclusive\_scan}}
\begin{cpp}
    (1)
template< class InputIt, class OutputIt,
          class BinaryOperation, class UnaryOperation >
OutputIt transform_inclusive_scan( InputIt first, InputIt last, OutputIt d_first,
                                   BinaryOperation binary_op, UnaryOperation unary_op );// (C++17 起)(C++20 前)
template< class InputIt, class OutputIt,
          class BinaryOperation, class UnaryOperation >
constexpr OutputIt transform_inclusive_scan( InputIt first, InputIt last,
                                             OutputIt d_first,
                                             BinaryOperation binary_op,
                                             UnaryOperation unary_op );// (C++20 起)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
          class BinaryOperation, class UnaryOperation >
ForwardIt2 transform_inclusive_scan( ExecutionPolicy&& policy,
                                     ForwardIt1 first, ForwardIt1 last, ForwardIt2 d_first,
                                     BinaryOperation binary_op, UnaryOperation unary_op );
(2)    (C++17 起)
(3)
template< class InputIt, class OutputIt,
          class BinaryOperation, class UnaryOperation, class T >
OutputIt transform_inclusive_scan( InputIt first, InputIt last, OutputIt d_first,
                                   BinaryOperation binary_op, UnaryOperation unary_op,
                                   T init );// (C++17 起)(C++20 前)
template< class InputIt, class OutputIt,
          class BinaryOperation, class UnaryOperation, class T >
constexpr OutputIt transform_inclusive_scan( InputIt first, InputIt last,
                                             OutputIt d_first,
                                             BinaryOperation binary_op,
                                             UnaryOperation unary_op,
                                             T init );//(C++20 起)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
          class BinaryOperation, class UnaryOperation, class T >
ForwardIt2 transform_inclusive_scan( ExecutionPolicy&& policy,
                                     ForwardIt1 first, ForwardIt1 last, ForwardIt2 d_first,
                                     BinaryOperation binary_op, UnaryOperation unary_op,
                                     T init );// (4)    (C++17 起)
\end{cpp}
以 unary\_op 变换范围 [first, last) 中的每个元素，然后用 binary\_op 在范围上计算包含前缀和，可选地以 init 为初值，并写结果到始于 d\_first 的范围。“包含”表明第 i 个元素包含于第 i 个和。

形式上，通过每个 [d\_first, d\_first + (last - first)) 中的迭代器 i 赋以下值

对于重载 (1-2) ，对于 [first, first + (i - d\_first + 1)) 中每个 j ，为 unary\_op(*j)... 在 binary\_op 上的的广义非交换和，
对于重载 (3-4) ，对于 [first, first + (i - d\_first + 1)) 中每个 j ，为 init, unary\_op(*j)... 在 binary\_op 上的广义非交换和，
其中广义非交换和 $GNSUM(op, a_1, \ldots, a_N)$ 定义如下：
    \begin{equation}
        \begin{cases}
            a_1\quad N = 1\\
            op(GNSUM(op,a_1,\ldots,a_K),GNSUM(op,a_M,\ldots,a_N))\quad 1Mk+1=M\leq N
        \end{cases}
    \end{equation}
换言之，能以任意顺序进行和运算，而若 binary\_op 非结合则行为为非确定的。

重载 (2, 4) 按照 policy 执行。这些重载仅若 std::is\_execution\_policy\_v<std::decay\_t<ExecutionPolicy>> (C++20 前)std::is\_execution\_policy\_v<std::remove\_cvref\_t<ExecutionPolicy>> (C++20 起) 为 true 才参与重载决议。

unary\_op 与 binary\_op 不应非法化范围 [first, last) 或 [d\_first, d\_first + (last - first)) 中的迭代器（含尾迭代器）或子范围，不修改其中的元素。否则行为未定义。

参数
\begin{itemize}
    \item first, last：求和的元素范围
    \item d\_first：目标范围起始；可以等于 first
    \item policy：所用的执行策略。细节见执行策略。
    \item init：初值
    \item unary\_op：一元函数对象 (FunctionObject) ，将要被应用到输入范围中的每个元素。返回类型必须可接受为 binary\_op 的输入。
    \item binary\_op：二元函数对象 (FunctionObject) ，将应用于 unary\_op 的结果、其他 binary\_op 的结果，还有 init ，若提供它。
\end{itemize}
类型要求
\begin{itemize}
    \item InputIt 必须满足遗留输入迭代器 (LegacyInputIterator) 的要求。
    \item OutputIt 必须满足遗留输出迭代器 (LegacyOutputIterator) 的要求。
    \item ForwardIt1 必须满足遗留向前迭代器 (LegacyForwardIterator) 的要求。
    \item ForwardIt2 必须满足遗留向前迭代器 (LegacyForwardIterator) 的要求。
    \item 若不提供 init ，则 decltype(first) 的值类型必须为可移动构造 (MoveConstructible) 而 binary\_op(unary\_op(*first), unary\_op(*first)) 必须可转换成 decltype(first) 的值类型
    \item T （若提供 init ） 必须满足可移动构造 (MoveConstructible) 的要求。binary\_op(init, unary\_op(*first)) 、 binary\_op(init, init) 和 binary\_op(unary\_op(*first), unary\_op(*first)) 都必须可转换为 T
\end{itemize}
返回值
指向最后被写入元素后一位置的迭代器。

复杂度
每个 binary\_op 和 unary\_op 应用 O(last - first) 次。

异常
拥有名为 ExecutionPolicy 的模板形参的重载按下列方式报告错误：
\begin{itemize}
    \item 若作为算法一部分调用的函数的执行抛出异常，且 ExecutionPolicy 为标准策略之一，则调用 std::terminate 。对于任何其他 ExecutionPolicy ，行为是实现定义的。
    \item 若算法无法分配内存，则抛出 std::bad\_alloc 。
注解
\end{itemize}
不应用 unary\_op 到 init 。

不同于 std::transform\_exclusive\_scan ，参数 init 出现于最后，因为它对此函数是可选的。
\cppfile{sample/numeric_transform_exclusive_scan_demo.cc}
计算示意图如\figref{fig:transform_inclusive_scan}：
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=\textwidth]{transform_inclusive_scan}
	\caption{std::transform\_inclusive\_scan示意图}
	\label{fig:transform_inclusive_scan}
\end{figure}
\subsection{\href{https://www.apiref.com/cpp-zh/cpp/algorithm/transform_exclusive_scan.html}{std::transform\_exclusive\_scan}}
\begin{cpp}
(1)
template< class InputIt, class OutputIt, class T,
          class BinaryOperation, class UnaryOperation>
OutputIt transform_exclusive_scan( InputIt first, InputIt last, OutputIt d_first, T init,
                                   BinaryOperation binary_op, UnaryOperation unary_op);// (C++17 起)(C++20 前)
template< class InputIt, class OutputIt, class T,
          class BinaryOperation, class UnaryOperation>
constexpr OutputIt transform_exclusive_scan( InputIt first, InputIt last, OutputIt d_first,
                                             T init, BinaryOperation binary_op,
                                             UnaryOperation unary_op);//(C++20 起)
template< class ExecutionPolicy,
          class ForwardIt1, class ForwardIt2,
          class T, class BinaryOperation, class UnaryOperation >
ForwardIt2 transform_exclusive_scan( ExecutionPolicy&& policy,
                                     ForwardIt1 first, ForwardIt1 last,
                                     ForwardIt2 d_first, T init,
                                     BinaryOperation binary_op, UnaryOperation unary_op );// (2)    (C++17 起)
\end{cpp}
以 unary\_op 变换范围 [first, last) 中的每个元素，然后在结果范围上用 binary\_op 以 init 为初值计算排除前缀和，并写入结果到始于 d\_first 的范围。“排除”表示第 i 个元素不包含于第 i 个和。

形式上，对于每个 [first, first + (i - d\_first)) 中的 j ，通过 [d\_first, d\_first + (last - first)) 中每个 i 赋 init, unary\_op(*j)... 在 binary\_op 上的广义非交换和的值，

其中广义非交换和 $GNSUM(op, a_1,\ldots, a_N)$ 定义如下：
\begin{equation}
    \begin{cases}
     a_1 \quad N = 1\\
    op(GNSUM(op, a_1, \ldots, a_K), GNSUM(op, a_M, \ldots, a_N))\quad 1 < K+1 = M \leq N
    \end{cases}
\end{equation}
换言之，和运算能以任意顺序进行，且若 binary\_op 非结合，则行为是非确定的。

重载 (2) 按照 policy 执行，此重载仅若 std::is\_execution\_policy\_v<std::decay\_t<ExecutionPolicy>> (C++20 前) std::is\_execution\_policy\_v<std::remove\_cvref\_t<ExecutionPolicy>> (C++20 起) 为 true 才参与重载决议。

unary\_op 与 binary\_op 不应非法化范围 [first, last) 或 [d\_first, d\_first + (last - first)) 中的迭代器（包含尾迭代器）或子范围，或修改其中的元素。否则行为未定义。

\textbf{参数}
\begin{itemize}
    \item first, last：要求和的范围
    \item d\_first：目标范围的起始，可以等于 first
    \item policy：所用的执行策略。细节见执行策略。
    \item init：初值
    \item unary\_op：一元函数对象 (FunctionObject) ，将要被应用到输入范围中的每个元素。返回类型必须可接受为 binary\_op 的输入。
    \item binary\_op：二元函数对象 (FunctionObject) ，将应用于 unary\_op 的结果、其他 binary\_op 的结果，还有 init 。
\end{itemize}
        类型要求
        \begin{itemize}
            \item InputIt 必须满足遗留输入迭代器 (LegacyInputIterator) 的要求。
            \item OutputIt 必须满足遗留输出迭代器 (LegacyOutputIterator) 的要求。
            \item ForwardIt1, ForwardIt2 必须满足遗留向前迭代器 (LegacyForwardIterator) 的要求。
            \item T 必须满足可移动构造 (MoveConstructible) 的要求。binary\_op(init, unary\_op(*first)) 、 binary\_op(init, init) 和 binary\_op(unary\_op(*first), unary\_op(*first)) 都必须可转换为 T 。
        \end{itemize}
\textbf{返回值}：指向最后写入元素后一位置元素的迭代器。

\textbf{复杂度}:应用 O(last - first) 次 binary\_op 和 unary\_op 。

\textbf{异常}:拥有名为 ExecutionPolicy 的模板形参的重载按下列方式报告错误：
\begin{itemize}
    \item 若作为算法一部分调用的函数的执行抛出异常，且 ExecutionPolicy 为标准策略之一，则调用 std::terminate 。对于任何其他 ExecutionPolicy ，行为是实现定义的。
    \item 若算法无法分配内存，则抛出 std::bad\_alloc 。
\end{itemize}
算法示意图如\figref{fig:transform_exclusive_scan}
\begin{remark}
不应用 unary\_op 到 init 。
\end{remark}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=\textwidth]{transform_exclusive_scan}
	\caption{std::transform\_exclusive\_scan示意图}
	\label{fig:transform_exclusive_scan}
\end{figure}
\subsection{\href{https://www.apiref.com/cpp-zh/cpp/numeric/gcd.html}{std::gcd}}
\begin{cpp}
template< class M, class N>
constexpr std::common_type_t<M, N> gcd(M m, N n); //(C++17 起)
\end{cpp}
计算整数 m 与 n 的最大公约数。例如5和10的最大公约数为5。m和n都是整数，若 m 与 n 均为零则返回零。否则返回 |m| 与 |n| 的最大公约数。
\begin{remark}
    \begin{itemize}
        \item 若 M 或 N 不是整数类型，或者若其中之一是（可有 cv 限定的） bool ，则程序为病式。
        \item 若 |m| 或 |n| 不能表示为 std::common\_type\_t<M, N> 类型的值，则行为未定义。
    \end{itemize}
\end{remark}
\subsection{\href{https://www.apiref.com/cpp-zh/cpp/numeric/lcm.html}{std::lcm}}
\begin{cpp}
template< class M, class N>
constexpr std::common_type_t<M, N> lcm(M m, N n); //(C++17 起)
\end{cpp}
计算整数 m 与 n 的最小公倍数。例如 5 和 10 的最小公倍数为20。

\textbf{参数}：m, n 为整数值。

\textbf{返回值}：若 m 或 n 为零，则返回零。否则，返回 |m| 与 |n| 的最小公倍数。
\begin{remark}
    \begin{itemize}
        \item 若 M 或 N 不是整数类型，或其中有（可为 cv 限定的） bool ，则程序出错。
        \item 若 |m| 、 |n| 或 |m| 和 |n| 的最小公倍数不能表示为 std::common\_type\_t<M, N> 类型的值，则行为未定义。
    \end{itemize}
\end{remark}
\subsection{\href{https://www.apiref.com/cpp-zh/cpp/numeric/midpoint.html}{std::midpoint}}
\begin{cpp}
template< class T >
constexpr T midpoint(T a, T b) noexcept;//(1)    (C++20 起)
template< class T >
constexpr T* midpoint(T* a, T* b);//(2)    (C++20 起)
\end{cpp}
计算整数、浮点或指针 a 与 b 的中点。
\begin{itemize}
    \item 此重载仅若 T 为 bool 以外的算术类型才参与重载决议。
    \item 此重载仅若 T 为对象类型才参与重载决议。若 T 为不完整类型则此重载的使用为谬构。
\end{itemize}
\textbf{参数}:a, b整数、浮点或指针值
\textbf{返回值}
\begin{itemize}
    \item a 与 b 和的一半。不出现上溢。若 a 与 b 拥有整数类型而和为奇数，则向 a 取整结果。若 a 与 b 拥有浮点类型，则至多出现一次不准确运算。
    \item 若 a 与 b 分别指向（就指针算术目的而言的）同一数组对象 x 的 x[i] 与 x[j] ，则返回指向 x[i+(j-i)/2] （或等价地为 x[std::midpoint(i, j)] ）的指针，其中除法向零取整。若 a 与 b 不指向同一数组对象，则行为未定义。
\end{itemize}
\textbf{异常}:不抛异常。
\begin{remark}
重载 (2) 在常见平台上能简单地实现为 return a + (b - a) / 2; 。然而不保证这种实现是可移植的，因为可以有一些平台上，可在其上创建元素数大于 PTRDIFF\_MAX 的数组，从而即使 b 与 a 均指向同一数组的元素 b - a 亦可导致未定义行为。
\end{remark}
\cppfile{sample/numeric_midpoint_demo.cc}

